#ifndef AFCORE_COMMON_ALGORITHM_MPSC_QUEUE_
#define AFCORE_COMMON_ALGORITHM_MPSC_QUEUE_

#include <atomic>
#include <utility>

#include "nocopyable.h"

namespace afcore {

/// @brief  多生产者单消费无锁队列
/// @note
/// C++ implementation of Dmitry Vyukov's lock free MPSC queue
/// http://www.1024cores.net/home/lock-free-algorithms/queues/non-intrusive-mpsc-node-based-queue
template<typename T>
class CMpscQueue
  : public CNocopyable {
public:
  /// @brief  构造函数
  CMpscQueue()
    : head_(new Node())
    , tail_(head_.load(std::memory_order_relaxed)) {
  }

  /// @brief  析构函数
  ~CMpscQueue() {
    T* output;
    while (this->Dequeue(output)) {
      ;
    }
    Node* front = head_.load(std::memory_order_relaxed);
    delete front;
  }

  /// @brief  入队
  /// @param  input       入队元素
  void Enqueue(T* input) {
    Node* node = new Node(input);
    Node* prev_head = head_.exchange(node, std::memory_order_acq_rel);
    prev_head->next.store(node, std::memory_order_release);
  }

  /// @brief  出队
  /// @param  result      出队元素 引用
  /// @return true        出队成功
  /// @return false       出队不成功
  bool Dequeue(T*& result) {
    Node* tail = tail_.load(std::memory_order_relaxed);
    Node* next = tail->next.load(std::memory_order_acq_rel);
    if (!next) {
      return false;
    }
    result = next->data;
    tail_.store(next, std::memory_order_release);
    delete tail;
    return true;
  }

private:
  /// @brief  队列节点
  struct Node {
    Node() = default;
    explicit Node(T* data_in)
      : data(data_in) {}

    T* data;                  ///< 节点数据
    std::atomic<Node*> next;  ///< 链表指针
  };

  std::atomic<Node*> head_;   ///< 头指针
  std::atomic<Node*> tail_;   ///< 尾指针
};

} // !namespace afcore

#endif //! AFCORE_COMMON_ALORITHM_MPSC_QUEUE_